\documentclass[UTF8]{ctexart}
\usepackage{geometry}
    \geometry{a4paper, left=2.5cm,right=2.5cm,top=2.54cm,bottom=2.54cm}
\usepackage{float}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{gbt7714}
    \bibliographystyle{gbt7714-numerical}
\usepackage{hyperref}
    \hypersetup{colorlinks, bookmarksnumbered, bookmarksopen}

\title{VAST Challenge 2023 MC1 可视化数据分析平台}
\author{苗沂坤\ 何骏\ 封璟\ 韩昊豫\ 张荐科}
\date{\today}

\begin{document}
\maketitle

我们选择了VAST Challenge 2023的Mini Challenge 1\cite{MiniChallenge}作为本工具需要解决的目标问题。该问题可重述如下：

\begin{quotation}
    \ttfamily

    FishEye致力于制止非法、未报告和未受管制（IUU）的捕捞活动。为此，FishEye收集了渔业、海洋工业和国际海上贸易的在线新闻文章，并使用自然语言处理工具来提取实体（人员和企业）的名称以及它们之间的关系，最后将这些信息转换为知识图谱。另外，FishEye还在得到的数据中添加了一些已知的非法捕鱼案例。FishEye希望使用可视化工具快速查看、理解和探索每个实体。如果可以发现某实体可能与IUU捕捞大概率有关，FishEye便可据此深入调查并阻止。

    FishEye希望使用可视化分析来查看、交互和理解实体及其上下文。应特别强调显示相关的上下文信息，隐藏不感兴趣或不相关的信息。可视化工具最好是动态、可交互的。

    本题需要在可视化工具中显示关注的实体的上下文信息，且应当在发现新实体时扩展看到的信息（如：若对某个与当前分析实体A高度相关的实体B感兴趣，工具应当容易地将分析实体由A转换到B）。根据得到的结果，回答下面四个问题：
\end{quotation}
我们编写的工具计划完成以下目标：
\begin{enumerate}
    \item 将知识图谱通过有效的可视化形式进行展现，并且对于信息进行有效整理、统计
    \item 提供方便、有效、可交互的可视化工具帮助分析人员探索实体上下文，使用关联分析、行为分析等分析方式并对于分析结果进行可视化展现
\end{enumerate}

\section{问题分析}

题目提供的所有数据都存储在一个JSON文件中。该文件的\verb|nodes|字段给出实体，\verb|links|字段给出实体间的关系。其中：实体可有id, type, country三个字段，仅id字段必然存在，type（若存在）可为person, organization, company, political\_organization, location, vessel, event, movement；实体间关系可有source, target, type三个字段，前两个必然存在，type（若存在）可为membership, partnership, ownership, family\_relationship。数据共3428个节点、11069条边。需要注意的是id字段是唯一标识符，但格式并不统一：对person，id是该人的名字；对organization，id是该组织的编号或名字；对location，id是该位置的UUID（格式为8-4-4-4-12，共32位16进制数），等等。

大致查看该JSON文件，并使用一些非可视化方法做简单分析，得到以下结论。

\subsection{拓扑结构符合大图的规律}

简单分析图节点度的分布得知：极少量节点的度极高，其余绝大部分节点的度很少。度最大的节点id为Ocean Fisheries Llc，有400条边与其相连；但90\%节点的度不超过13，80\%节点的度不超过7，50\%节点的度不超过3。这符合大图的一般规律。

这要求可视化工具可以同时展示度极大和极小的节点：度小时，不能留下太多空白；度大时，又不能太过紧密，使得视觉元素交叠而失效。

\subsection{数据中存在乱码和无意义项}

使用chardet库，有99\%信心判断JSON的编码为utf-8.但以该编码打开文件之后，仍然发现了大量乱码。有些id完全由乱码组成，如\verb|œLï|；有些id中含有乱码，但仍能表达语义，如\verb|âillegalâ|, \verb|âvictimâ|。另外，有些节点的id意义不明，尤其是type为event的id，例如：Storm, Stuff, course years, entire 2036, event, Hubble, Say……很难看出其到底表示的何种语义。

这要求我们对数据做清洗。然而清洗可能会洗掉有用的信息，尤其是清洗掉id中含有乱码，但仍能表达语义的节点时。最理想的情况是：提过多种清洗的强度，如完全不清洗、清洗id完全由乱码组成的节点、清洗id中含有乱码的节点、清洗id中含有乱码或id意义不明的节点，等等，让使用可视化工具的用户来选择。

\subsection{只能通过非直接信息分析非法捕鱼}

数据集中没有显式表明（如"illegal": true等方式）哪些节点或联系是非法捕鱼。说明必须从非直接的信息，如节点id、节点间联系等方面挖掘非法捕鱼的特征。

\subsection{假设-检验法}

由上分析，在开发工具的过程中，可以使用假设-检验法：首先粗略查看数据集的性质，之后再编写可视化代码验证之。若符合假设，保留该可视化，在其基础上开发；否则放弃。迭代此过程，直至完成。

\section{项目功能介绍}

根据问题分析，经过多次迭代后，我们的成品工具界面如下：

\begin{figure}[H]
    \centering
    \includegraphics[width=0.9\textwidth]{2023-06-30_162343.png}
    \caption{工具界面}
    \label{fig:intro}
\end{figure}
该工具大致分为左右两栏。左栏从上到下为：过滤栏、总体力导向图；右栏从上到下为：搜索框和当前选中节点信息、子图节点相关度表、力导向图子图和t-SNE图\cite{vandermaatenVisualizingDataUsing2008}、相关节点柱状图和相关关系强度直方图。

\subsection{过滤栏}

选择想要展示在力导向图（总图和子图）中的节点和边的类型，以及想要强调的节点类型。其中，节点类型NodeType、边类型EdgeType可多选，强调节点Emphasize只能选一类。每次改变后，点击最下方的“确认”按钮使得改动生效，当前选中的节点不会变动。

过滤栏是最简单的数据选择方法。通过选择想要展示的节点和边的类型、选择想要强调的节点的类型，用户可以专注于自己想要了解的信息、暂时忽略不想关注的信息，也能减少主图中的视觉元素，避免大量视觉信息互相交叠而失效。

\subsection{总体力导向图}

该图展示了节点和边的总体拓扑结构，其中的节点和边由上面的过滤栏确定。图的左上角为图例，标注不同颜色表示的类型。当前节点是用户现在关注的节点，其大小最大；过滤栏中确定的“强调节点”大小大于剩余节点。用户可以把握整个数据集的结构，粗略但全面地了解图中哪些节点较为关键、度较多、更加中心，等等。

此图支持大量\textbf{可交互操作}：鼠标左键在图背景上按住并拖动，可以平移图中的所有元素；鼠标放在图中滚动滚轮，可以放大或缩小整张图；将鼠标悬浮在节点上，节点颜色会变浅，同时显示节点的id，提示该节点被鼠标选中，此时左击该节点，当前节点即变换；可以拖拽一个节点，在一定限度内改变其在图中的位置，以避免节点的边被遮挡。

\subsection{搜索框和当前选中节点信息}

本部分在中括号中展示了选中节点的id和type：[type:id]。此外，还能在此处选定下方力导向图子图的跳数，以及搜索特定的节点（此处没有模糊搜索，搜索关键字必须与目标id完全一致）。

\subsection{子图节点相关度表}

本\textbf{可交互}表格展示了子图中的详细信息，包括了id、类别、距离以及相关程度，其中相关程度是通过边权数据经过PageRank算法得到，展示了子图中的各个实体和所选中的节点的联系紧密程度。相关程度数据可以使得使用本工具的分析人员很容易得到可能有兴趣的数据。

表格支持\textbf{点击功能}，可以交互地重新选择当前选中的节点，以进一步分析感兴趣的数据点。同时，表格支持模糊搜索、按照类型、距离、相关程度按照降序或者升序排序，进一步提高了使用效率。

表格可分多页，这使得表格可以同时展示度较小和度极大的节点。

\subsection{力导向图子图和t-SNE图}

子图展示了选中节点的局部拓扑结构，和主图支持一样的操作，如平移、缩放、点击切换当前选中的节点等。这样可以使得分析人员对于当前节点的局部信息有更加直观的认识。

后续我们还从两个角度提供了\textbf{可交互的}t-SNE图，为分析人员提供该选中实体可能的行为模式判断依据。这里的所提及的行为模式，可以从相邻节点的类型和与相邻节点之间的联系类型两方面入手。

首先，将统计每一种相邻节点类型的数量或与相邻节点每一种联系的数量（如从属、合作等），将其转化为一个高维向量并进行归一化操作，这个得到的向量可以一定程度上代表这个节点的\emph{行为模式}。对这些高维向量进行主成分分析并使用t-SNE可视化方法降维嵌入至二维平面中，可以将具有相同行为模式的实体聚集在一起，使得分析人员可以较为简易地对于当前实体局部节点的行为模式有清晰的认识。

为了进一步分析每一类别的\emph{行为模式}，两张t-SNE图片都支持\textbf{刷选功能}，其效果是对于表格中的数据进行过滤（即仅展示刷选数据及当前节点），分析人员可以通过点击表格中感兴趣的节点进行进一步分析。

\subsection{相邻节点类型柱状图和相关关系强度直方图}

最后，我们的工具还提供了两幅统计图为分析人员提供进一步的信息参考。首先是提供了关于当前选择节点相邻节点类型的柱状图，可以使得对于当前节点的总体行为有大致认识。其次，我们还提供了相关关系强度直方图，为分析人员提供当前子图各节点的联系紧密程度的统计信息，与柱状图相互进行印证。



\section{系统具体实现}

本工具分为前端和后端，这便于在未来将本工具部署在服务器上。其中，后端基于Python的Flask框架开发，前端基于JavaScript可视化库d3\cite{D3ObservableJavaScript}开发。两部分联系紧密、分工明确，前端界面直观、后端处理高效。

\subsection{预处理}

存储数据的JSON文件存储在后端。工具启动时，后端会先于一切用户操作预处理数据。首先，后端从JSON中构造出图结构，将图划分为若干个连通的子图，并删除节点数量过少的连通子图。这一步意在删除无关信息，消除可视化结果中的干扰项。之后，极其保守地合并节点：如果一个type为person的节点是悬挂点（度为1），则删除该节点和悬挂边，将其信息并入其悬挂的节点；如果一个type为person的节点仅与另外的两个节点A, B相连，则删除该节点和两条边，在A和B之间建立一新条边以表示原先关系。这一步减少了少量的处理负担。

预处理得到的结果会取代原始数据，作为之后一切处理的源数据。

\subsection{前后端数据通信}

前端的主要功能是作为和用户的接口，向后端发送用户的选择数据，如过滤表本身、当前节点对应的x-hop子图；还有从后端接收数据，如过滤表对应的数据点，t-SNE图。一次使用过程可描述为：前端将过滤表发送给后端，后端接收后，根据过滤条件返回对应的节点和边；前端接收到这些信息，使用d3可视化之，绘制力导向图，之后处理暂停直到用户选择当前节点；用户选择当前节点后，由前端构造该节点x-hop子图与柱状图，并将子图发回给后端，后端根据子图计算t-SNE图和直方图；最后，前端接收到t-SNE图和直方图的计算结果并显示，结束。

此套流程的优点是：在保证速度的同时，尽量减少了前后端的通信量。例如：用户在选择当前节点时，前端不会再向后端请求数据，因为过滤表并未改变，这意味着后端不需知道当前节点变化，减少了大量通信；当前节点改变会导致力导向图子图改变，因为后端不知道当前节点变化，故由前端负责生成当前节点对应的x-hop子图；考虑到前端的处理能力可能较差，选用后端计算t-SNE图和直方图，这要求把前端产生的子图传回后端，并在计算完成后从后端接收结果。在可行的范围内，这个方案保有了良好的响应速度和流畅程度。

\subsection{后端算法}

后端在接收到前端传来的子图后，调用对应算法，生成t-SNE图和直方图所需要的信息，通过http传输给前端绘制。

\subsubsection{t-SNE图}

后端会生成两张t-SNE图，分别对应当前节点的相关节点和边。其计算较为简单：首先，对子图中的每个节点A，生成对应向量，其维数是type数（相关节点t-SNE图为子图中所有节点的type数，边t-SNE图为子图中全部边的type数），每维的含义是A连接对应type节点的数量，如果维数小于2则报错，提示type数过少；之后，使用PCA提取主成分，输入t分布后聚类得到各个点的坐标。

t-SNE图的作用是直观地展示相关节点之间的联系，理想情况下，可以在子图中看到明显的聚类，表示当前节点的相关节点可划分为若干类。如果某个聚类中存在非法捕捞的节点，则可以怀疑该聚类中的其它节点也有一定嫌疑。

\subsubsection{直方图}

直方图由和当前节点相连的边的type和边权得到。将由这些边组成的子图视为无向图，初态将当前节点权重设为1，其余全部节点设为0.之后，在图上运行PageRank直到收敛。

直方图的作用是量化联系强度，其利用了边权，是对t-SNE的补充。如果观察到在

\section{实际案例分析}
假设分析人员对于组织“8327”较为感兴趣，希望得到行为可疑个人或组织。因此，首先选择的\emph{节点类型}为个人、组织、船只、事件；选择的\emph{联系}主要是成员、合作、从属关系；假设我们更加关注个人的行为，可以将个人进行突出显示。

对于原图进行必要的过滤后，搜索组织“8327”，生成其距离为1的相邻子图进行分析，如图\ref{ex1}所示。

\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{ex1.png}
    \caption{组织“8327”的局部联系图}
    \label{ex1}
\end{figure}

得到子图后，我们首先在表格中找到了可能的非法事件。点击该非法事件，可以生成关于此非法事件的子图。假设分析人员对于个人较为感兴趣，可以在表格中搜索“person”，按照相关度从高到低展示与此事件联系紧密的可以人员，如图\ref{ex2}所示。

\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{ex2.png}
    \caption{可疑的事件}
    \label{ex2}
\end{figure}

找到可疑的人物，我们可疑根据可疑人物的行为特征继续找出更多的可疑人物或组织。首先我们可以将子图设置为2-hop以得到更多信息，观察可疑人物所在的集群，对于该集群进行刷选，得到行为特征类似的个人和组织，如图\ref{ex3}所示。

\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{ex3.png}
    \caption{根据可疑人物行为特征继续搜索}
    \label{ex3}
\end{figure}

我们也可以得到与可疑人物关联的船只，可见该船只与非法事件联系也非常紧密，在某种程度上也印证了我们的猜想。通过分析与该船只联系的组织或个人，可能可以得到更多信息，如图\ref{ex4}所示。

\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{ex4.png}
    \caption{分析可疑的船只}
    \label{ex4}
\end{figure}


\section{总结}

首先，我们的可视化工具从数据形式以及具体问题特点出发，将难以分析的图结构数据简化为较为友好的展现形式，并且根据图结构的特点提供了局部结构展示、局部数据统计分析、行为模式分析等有效分析方式，允许分析人员从多角度直观地进行具体分析。

其次，我们的可视化工具设计注重可交互和各可视化形式的紧密联系。我们可视化工具基本都提供了与用户的交互功能，如点击、刷选、缩放，能够帮助用户聚焦于自己感兴趣的信息，排除其它干扰。在此基础上，各个可视化形式紧密联系，如局部信息可以通过点击力导向图中的点或表格中的数据进行选择；t-SNE图的刷选结果可以在表格中得以体现。

最后，我们的可视化系统设计较为合理，分为前端和后端。前端主要进行数据展示，后端主要进行复杂的数据处理工作。系统分工合理、接口完善、可拓展性较强，系统设计总体而言较为成功。

综上所述，我们设计的可视化工具能够很好地协助分析人员对于图数据进行分析，并且在实际案例中展现了其可行性。总体而言，本次课程设计较为成功。

\bibliography{ref.bib}

\end{document}